package busquedasciegas.anchura;

// Segundo cambio para probar svn

import java.util.*;

public class EstadoPuzzle {
	
	EstadoPuzzle padre;
	int[][] tablero;
	LinkedList<EstadoPuzzle> hijos;
	boolean visitado;
	
	
	public EstadoPuzzle(LinkedList<Integer> tablero){
		LinkedList<Integer> tableroProv = tablero;
		int lado = (int) Math.sqrt(tableroProv.size());
		this.tablero = new int[lado][lado];
		
		for(int i = 0; i < lado; i++)
			for(int j = 0; j < lado; j++)
				this.tablero[i][j] = tableroProv.get((i * lado) + j);
				
		this.padre = null;
		this.hijos = new LinkedList<EstadoPuzzle>();
		this.visitado = false;
	}
	
	public EstadoPuzzle(int[][] tablero, EstadoPuzzle padre){
		this.tablero = tablero;
		this.padre = padre;
		this.hijos = new LinkedList<EstadoPuzzle>();
		this.visitado = false;
	}
	
	
	public boolean isVisitado() {
		return visitado;
	}

	public void setVisitado(boolean visitado) {
		this.visitado = visitado;
	}

	/**
	 * Esta función genera un estado inicial (tablero)
	 * en un orden aleatorio.
	 * @return Un estado inicial.
	 */
	public EstadoPuzzle generarNodoInicial(int cuadrados, boolean aleatorio){
		Aleatorio generador = new Aleatorio();
		LinkedList<Integer> tablero = new LinkedList<Integer>();
		LinkedList<Integer> temporal;
		for (int i = 0; i < cuadrados; i++){
			tablero.add(i);
		}
		if (aleatorio){
			temporal = generador.aleatoria(tablero);
			tablero = temporal;
		}
		EstadoPuzzle e = new EstadoPuzzle(tablero);
		return e;
	}
	
	
	/**
	 * Esta función aplica los operadores a un estado
	 * con el fin de obtener nuevos estados (descendientes).
	 * @param Variable de tipo Estado.
	 * @return Una lista con los hijos del padre.
	 */
	public LinkedList<EstadoPuzzle> generarDescendientes(){
		
		// Encontrar la posición del hueco en el tablero
		int iHueco = 0, jHueco = 0;
		int lado = this.tablero.length;
		for (int i = 0; i < lado; i++){
			for (int j = 0; j < lado; j++){
				if (this.tablero[i][j] == 0){
					iHueco = i;
					jHueco = j;
				}
			}
		}
		//System.out.println(iHueco);
		//System.out.println(jHueco);
		/* El máximo número de descendientes (jugadas) de
		 *  un estado en es puzzle es 4 */
		LinkedList<EstadoPuzzle> descendientes = new LinkedList<EstadoPuzzle>();
		EstadoPuzzle hijo1, hijo2, hijo3, hijo4;
	
		int[][] temp = copiarArreglo(lado);
		
		if ((iHueco == 0) && (jHueco == 0)){
			temp[0][0] = this.tablero[0][1];
			temp[0][1] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			descendientes.add(hijo1);

			temp = copiarArreglo(lado);
			temp[0][0] = this.tablero[1][0];
			temp[1][0] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo2);
	
		}
		else if ((iHueco == 0) && (jHueco == lado-1)){
			temp[0][lado-1] = this.tablero[0][1];
			temp[0][1] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			temp = copiarArreglo(lado);
			temp[0][lado-1] = this.tablero[1][lado-1];
			temp[1][lado-1] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
		}
		else if ((iHueco == lado-1) && (jHueco == 0)){
			temp[lado-1][0] = this.tablero[lado-2][0];
			temp[lado-2][0] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			
			temp = copiarArreglo(lado);
			temp[lado-1][0] = this.tablero[lado-1][1];
			temp[lado-1][1] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
			
		}
		else if ((iHueco == lado-1) && (jHueco == lado-1)){
			temp[lado-1][lado-1] = this.tablero[lado-2][lado-1];
			temp[lado-2][lado-1] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			temp = copiarArreglo(lado);
			temp[lado-1][lado-1] = this.tablero[lado-1][lado-2];
			temp[lado-1][lado-2] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
		}
		else if (((1 <= iHueco) && (iHueco <= lado-2)) &&
				((1 <= jHueco) && (jHueco <= lado-2))){
			temp[iHueco][jHueco] = this.tablero[iHueco+1][jHueco];
			temp[iHueco+1][jHueco] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			temp = copiarArreglo(lado);
			temp[iHueco][jHueco] = this.tablero[iHueco-1][jHueco];
			temp[iHueco-1][jHueco] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			temp = copiarArreglo(lado);
			temp[iHueco][jHueco] = this.tablero[iHueco][jHueco-1];
			temp[iHueco][jHueco-1] = 0;
			hijo3 = new EstadoPuzzle(temp, this);
			
			temp = copiarArreglo(lado);
			temp[iHueco][jHueco] = this.tablero[iHueco][jHueco+1];
			temp[iHueco][jHueco+1] = 0;
			hijo4 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
			descendientes.add(hijo3);
			descendientes.add(hijo4);
		}
		else{
			if (iHueco == 0){
				temp[iHueco][jHueco] = this.tablero[iHueco][jHueco-1];
				temp[iHueco][jHueco-1] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco][jHueco+1];
				temp[iHueco][jHueco+1] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco+1][jHueco];
				temp[iHueco+1][jHueco] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			else if (iHueco == lado-1){
				temp[iHueco][jHueco] = this.tablero[iHueco][jHueco-1];
				temp[iHueco][jHueco-1] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco][jHueco+1];
				temp[iHueco][jHueco+1] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco-1][jHueco];
				temp[iHueco-1][jHueco] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			else if (jHueco == 0){
				temp[iHueco][jHueco] = this.tablero[iHueco-1][jHueco];
				temp[iHueco-1][jHueco] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco+1][jHueco];
				temp[iHueco+1][jHueco] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco][jHueco+1];
				temp[iHueco][jHueco+1] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			else if (jHueco == lado-1){
				temp[iHueco][jHueco] = this.tablero[iHueco-1][jHueco];
				temp[iHueco-1][jHueco] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco+1][jHueco];
				temp[iHueco+1][jHueco] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = copiarArreglo(lado);
				temp[iHueco][jHueco] = this.tablero[iHueco][jHueco-1];
				temp[iHueco][jHueco-1] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			
		}
		return descendientes;
		
	}

	private int[][] copiarArreglo(int lado) {
		int[][] temp = new int[lado][lado];
		for(int i = 0; i < lado; i++)
			for(int j = 0; j < lado; j++)
				temp[i][j] = this.tablero[i][j];
		return temp;
	}
	
	public String toString(){
		String tableroString = "";
		for (int i = 0; i < this.tablero.length; i++){
			for (int j = 0; j < this.tablero[0].length; j++){
				tableroString = tableroString + this.tablero[i][j] + " ";
			}
			tableroString = tableroString + "\n";
		}
		return tableroString;
	}
	
	public static void main(String[] args) {
		LinkedList<Integer> tablero = new LinkedList<Integer>();
		tablero.add(0);
		tablero.add(1);
		tablero.add(2);
		tablero.add(3);
		tablero.add(4);
		tablero.add(5);
		tablero.add(6);
		tablero.add(7);
		tablero.add(8);
//		tablero.add(9);
//		tablero.add(10);
//		tablero.add(11);
//		tablero.add(12);
//		tablero.add(13);
//		tablero.add(14);
//		tablero.add(15);
		
		EstadoPuzzle e = new EstadoPuzzle(tablero);
//		for(int i = 0; i < 4; i++)
//			for(int j = 0; j < 4; j++)
//				System.out.println(e.tablero[i][j]);
		EstadoPuzzle nuevoEstado;
		nuevoEstado = e.generarNodoInicial(9, true);
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				System.out.println(nuevoEstado.tablero[i][j]);
		LinkedList<EstadoPuzzle> desc = nuevoEstado.generarDescendientes();
		System.out.println("--- Hijos ---");
		for (EstadoPuzzle hijo : desc) {
			System.out.println("Hijo: ");
			System.out.print(hijo);
		}
		
		
	}
}
